De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat

vragen bekijken

een vraag stellen

hulpjes

zoeken

FAQ

links

twitter

boeken

help

inloggen

colofon

Reageren...

Re: Formules voor ellips en hyperbool

Hoi Anneke,
Heel erg bedankt voor je snelle reactie. Ik weet niet of ik zo weer door kan reageren met een nieuwe vraag, maar probeer het gewoon. Want, helaas stuit ik nu nog op een onduidelijkheid, die gaat als volgt. Als M mijn boodschap is, C de codetekst die ik uiteindelijk verzend, e de coderingscode is en d mijn decoderingscode krijg je met het coderen en decoderen de volgende 'formules':

C = M^e (mod n) en C^d (mod n) = M'

nu geldt dus M' = M.

Dit kun je bewijzen door:

M’ $\equiv$ C^d (mod n) $\equiv$ (M^e)^d (mod n) $\equiv$ M^e·d (mod n)

M^e·d = M^{(1+k$\phi$(n))}

M^{(1+k$\phi$(n))} =(M^$\phi$(n))^k · M $\equiv$ (1)^k · M (mod n) $\equiv$ 1 (mod n)

Op zich snap ik dit voor een groot gedeelte. Mij is onduidelijk waar nu precies wel en geen '(mod n)' bijhoort. Of mag het overal tussen de $\equiv$-tekens staan?
En waarom is (M^$\phi$(n)) ^k = 1^k?

Alvast hartstikke bedankt!
Groetjes,

Antwoord

Hoi,

De onderliggende wiskunde van deze RSA-encryptie is de stelling van Euler, een veralgemening van de kleine stelling van Fermat.

Als a en n onderling ondeelbaar zijn (ggd(a,n)=1), dan is a^$\phi$(n)=1 (mod n). In het bijzonder geldt dan voor je welgevormde bericht M dat M^$\phi$(n)=1 (mod n). (Of je dat met $\equiv$ of = schrijft, maakt volgens mij weinig uit. Ik zou die $\equiv$ voor het gemak en de duidelijkheid nooit gebruiken. Soms laten ze de (mod n) weg als het duidelijk is, maar het kan geen kwaad om dat er altijd bij te zetten.)

De truuk (en de moeilijkheid) bestaat erin 2 getallen e en d te vinden zodat e.d=1 (mod $\phi$(n)) of anders genoteerd: e.d=1+k.$\phi$(n) voor een zekere gehele k. De kracht van de code volgt uit het feit dat het praktisch te lang duurt om d te berekenen als je n en e kent.

Met C en M' zoals jij die definieerde, hebben we dan (alles (mod n)):
M'=C^d=(M^e)^d=M^{1+k.$\phi$(n)}=M.(M^$\phi$(n))^k=M.1^k=M.

Groetjes,
Johan

Gebruik dit formulier alleen om te reageren op de inhoud van de vraag en/of het antwoord hierboven. Voor het stellen van nieuwe vragen kan je gebruik maken van een vraag stellen in het menu aan de linker kant. Alvast bedankt!

Reactie:
	Klik eerst in het tekstvlak voordat je deze knopjes en tekens gebruikt. Pas op: onderstaande knopjes en speciale karakters werken niet bij ALLE browsers! áâæàåãäßçéêèëíîìïñóôòøõöúûùüýÿ½¼¾€£®© $\forall$$\exists$$\neg$$\wedge$$\vee$$\Leftrightarrow$$\Leftarrow$$\Rightarrow$$\emptyset$$\cap$$\cup$$\supset$$\supseteq$$\not\subset$$\subset$$\subseteq$$\in$$\notin$ $\sim$$\equiv$$\ne$$\pm$$\times$$\div$$\otimes$$\oplus$$\pi$$\leftarrow$$\uparrow$$\to$$\downarrow$ $\sqrt{}$$\sum$$\prod$$\infty$$\smallint$$\Delta$$\nabla$$\partial$$\angle$$\bot$$\cong$$\widehat p$ $\alpha$$\beta$$\gamma$$\delta$$\varepsilon$$\phi$$\theta$$\lambda$$\mu$$\rho$$\sigma$$\tau$$\omega$$\chi$$\Gamma$$\vartheta$$\Lambda$$\Omega$$\Psi$$\zeta$ $\mathbf{N}$ $\mathbf{Z}$ $\mathbf{Q}$ $\mathbf{R}$ $\mathbf{C}$
Categorie:	Vlakkemeetkunde
Ik ben:	-------------- Maak een keuze --------------- Leerling onderbouw vmbo-havo-vwo Leerling bovenbouw vmbo Leerling bovenbouw havo-vwo Leerling mbo Student hbo Student universiteit 1ste graad ASO-TSO-BSO Overige TSO-BSO 2de graad ASO 3de graad ASO Student Hoger Onderwijs België Student universiteit België Cursist vavo Docent Ouder Iets anders Beantwoorder
Naam:
Emailadres:
Datum:	19-5-2024